/**
 * 395. 至少有 K 个重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class Solutions_395 {
    public static void main(String[] args) {
//        String s = "aaabb";
//        int k = 3;  // output: 3

        String s = "ababbc";
        int k = 2;  // output: 5

//        String s = "aaaaaaaaaaaabcdefghijklmnopqrstuvwzyz";
//        int k = 3;  // output: 12

//        String s = "aaaaaaaaaaaabcdefghijklmnopqrstuvwzyzaa";
//        int k = 3;  // output: 12

        int result = longestSubstring(s, k);
        System.out.println(result);
    }

    /**
     * 解题思路：分治算法
     * 关键：通过两个 while 循环，将最左、最右两侧出现次数小于 k 次的字母排除掉，
     * 即缩小 [left, right] 的范围
     * 最终一个 for 循环用于处理 [left, right] 区间字符串内，出现次数少于 k 次的字母
     * 以字符串 "aaaaaaaaaaaabcdefghijklmnopqrstuvwzyzaa" 为例
     *
     * 1. 两个 while 循环不能缩小区间
     * 2. for 循环判断出字母 b 在字符串中小于 k 次，那么以 b 所在的索引进行划分
     * 3. 得到 [left, i - 1]，[i + 1, right] 的两个子串，并继续递归处理
     *      3.1 最终结果也一定在 [left, i - 1]，[i + 1, right] 中产生
     */
    public static int longestSubstring(String s, int k) {
        char[] arr = s.toCharArray();
        int res = divide(arr, 0, arr.length - 1, k);
        return res;
    }

    public static int divide(char[] arr, int left, int right, int k) {
        if (right - left + 1 < k) {
            // 总长度小于 k
            return 0;
        }
        int[] cnt = new int[26];
        for (int i = left; i <= right; i++) {
            cnt[arr[i] - 'a'] ++;
        }
        // 剪枝：缩小 [left, right] 范围
        // 通过两个 while 循环，能将最左、最右两侧出现次数小于 k 次的字母排除掉
        while (left < right && cnt[arr[left] - 'a'] < k) {
            left ++;
        }
        while (left < right && cnt[arr[right] - 'a'] < k) {
            right --;
        }
        if (right - left + 1 < k) {
            return 0;
        }
        // 该 for 循环用于处理 [left, right] 内，出现次数少于 k 次的字母
        // 即上面两个 while 循环未处理掉的
        for (int i = left; i <= right; i++) {
            if (cnt[arr[i] - 'a'] < k) {
                int leftRes = divide(arr, left, i - 1, k);
                int rightRes = divide(arr, i + 1, right, k);
                // [left, right] 中存在出现次数少于 k 次的字母
                return Math.max(leftRes, rightRes);
            }
        }
        // 即 [left, right] 中的全部字母都最少出现了 k 次，
        // 那么 [left, right] 满足要求，且一定是最长的子串
        return right - left + 1;
    }
}
